Inhibitors of histone deacetylases (HDACs) are a new class of anticancer agents that affect gene regulation. We had previously reported the first simple synthetic HDAC inhibitors with in vitro activity at submicromolar concentrations. Here, we present structure-activity data on modifications of a phenylalanine-containing lead compound including amino acid amides as well as variations of the amino acid part. The compounds were tested for inhibition of maize HD-2, rat liver HDAC, and for the induction of terminal cell differentiation and inhibition of proliferation in Friend leukemic cells. In the amide series, in vitro inhibition was potentiated up to 15-fold, but the potential to induce cell differentiation decreased. Interestingly, an HDAC class selectivity was indicated among some of these amides. In the amino acid methyl ester series, a biphenylalanine derivative was identified as a good enzyme inhibitor, which blocks proliferation in the submicromolar range and is also a potent inducer of terminal cell differentiation.